package listbyorder.access201_300.test234;

import listbyorder.utils.ListNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/26 19:38
 */
public class Solution1 {

    // 反转链表实现
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        boolean flag = true;
        // 快慢指针找到中间节点
        ListNode c1 = head;
        ListNode c2 = head;
        while (c1.next != null && c1.next.next != null) {
            c1 = c1.next.next;
            c2 = c2.next;
        }
        ListNode tail = c2.next;
        c2.next = null;
        c1 = reverse(tail);
        ListNode t1 = c1;
        ListNode t2 = head;
        while (t1 != null && t2 != null) {
            if (t1.val != t2.val) {
                flag = false;
                break;
            }
            t1 = t1.next;
            t2 = t2.next;
        }
        c2.next = reverse(c1);
        return flag;
    }

    private ListNode reverse(ListNode node) {
        if (node == null || node.next == null) return node;
        ListNode pre = null;
        ListNode next = null;
        while (node != null) {
            next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }
}
